class Queue():
    class Node():
        def __init__(self,value=None):
            self.prev=None#双端队列
            self.next=None#后继元素
            self.value=value

    def __init__(self):
        self.front=None
        self.tail=None
        self.size=0

    def enqueue_tail(self, val):
        new_node = self.Node(val)
        if self.is_empty():
            self.front = new_node
            self.tail = new_node
        #双端循环队列新增
        new_node.next = self.front
        new_node.prev = self.tail
        self.tail.next = new_node
        self.front.prev = new_node
        self.tail = new_node
        
        self.size += 1
        return True
    
    def enqueue_front(self, val):
        new_node = self.Node(val)
        if self.is_empty():
            self.front = new_node
            self.tail = new_node
        #双端循环队列新增
        new_node.next = self.front
        self.front.prev = new_node
        new_node.prev = self.tail
        self.tail.next = new_node
        self.front = new_node
        
        self.size += 1
        return True

    def dequeue_front(self):
        if self.is_empty():
            return None
        
        data = self.front.value
        #双端循环队列修改
        if self.size is 1:
            self.front = None
            self.tail = None
        else:
            new_front = self.front.next
            new_front.prev = self.tail
            self.tail.next = new_front
            self.front = new_front
        self.size -= 1
        return data
    
    def dequeue_tail(self):
        if self.is_empty():
            return None
        
        data = self.tail.value
        #双端循环队列修改
        if self.size is 1:
            self.tail = None
            self.front = None
        else:
            new_tail = self.tail.prev
            new_tail.next = self.front
            self.front.prev = new_tail
            self.tail = new_tail
        self.size -= 1
        return data

    def peek_front(self):
        if self.is_empty():
            return None
        return self.front.value
    
    def peek_tail(self):
        if self.is_empty():
            return None
        return self.tail.value
    
    def is_empty(self):
        return self.size == 0
    
    def length(self):
        return self.size
    
    def clear(self):
        self.front = None
        self.tail = None
        self.size = 0

        return True
    
    def is_full(self):
        pass

    def contains(self, value):
        cur_node = self.front
        for _ in range(self.size):
            if cur_node.value == value:
                return True
            cur_node = cur_node.next
        
        return False